//以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返
//回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。 
//
// 
//
// 示例 1： 
//
// 
//输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
//输出：[[1,6],[8,10],[15,18]]
//解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
// 
//
// 示例 2： 
//
// 
//输入：intervals = [[1,4],[4,5]]
//输出：[[1,5]]
//解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。 
//
// 
//
// 提示： 
//
// 
// 1 <= intervals.length <= 104 
// intervals[i].length == 2 
// 0 <= starti <= endi <= 104 
// 
// Related Topics 数组 排序 
// 👍 1045 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[][] merge(int[][] intervals) {
        int[][] sortArray = sortArray(intervals);
        List<int[]> ans = new ArrayList<>();

        int[] temp = new int[2];
        temp[0] = sortArray[0][0];
        temp[1] = sortArray[0][1];

        for (int i = 1; i < sortArray.length; i++) {
            if (sortArray[i][0] > temp[1]) {
                ans.add(temp);
                temp = new int[2];
                temp[0] = sortArray[i][0];
                temp[1] = sortArray[i][1];
            } else if (sortArray[i][1] > temp[1]) {
                temp[1] = sortArray[i][1];
            }
        }

        ans.add(temp);


        return ans.toArray(new int[ans.size()][2]);
    }


    static int[][] temp;

    public static int[][] sortArray(int[][] nums) {
        int len = nums.length;
        temp = new int[len][2];
        mergeSort(nums, 0, len-1);
        return nums;

    }

    public static void mergeSort(int[][] nums, int l, int r) {
        if (r <= l) {
            return;
        }
        if (l+1 == r) {
            if (nums[l][0] > nums[r][0]) {
                int[] temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;

            }
            return;
        }
        int len = r - l + 1;
        int mid = (r + l) / 2;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);

        int index = l;
        int ileft = l;
        int iright = mid + 1;
        while (ileft <= mid && iright <= r) {

            if (nums[ileft][0] > nums[iright][0]) {
                temp[index++] = nums[iright];
                iright++;
            } else {
                temp[index++] = nums[ileft];
                ileft++;
            }
        }

        while (iright <= r) {
            temp[index++] = nums[iright];
            iright++;
        }

        while (ileft <= mid) {
            temp[index++] = nums[ileft];
            ileft++;
        }

        for (int i = l; i <= r; i++) {
            nums[i] = temp[i];
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
